package com.cat.chapter036;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author cat
 * @description https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
 * @create 2025/6/14 17:56
 * @since JDK17
 */

public class Solution02 {
    static final int MAXN = 2001;
    TreeNode[] queue = new TreeNode[MAXN];
    int l = 0;
    int r = 0;
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return ans;
        }
        boolean isReverse = false;
        queue[r++] = root;  // 将根节点压入队列
        while (l < r) {
            int j = r;
            List<Integer> list = new ArrayList<>();
            ans.add(list);
            while (l < j) { // 一次处理一层
                TreeNode node = queue[l++];
                list.add(node.val);
                if (node.left != null) {    // 有左加左
                    queue[r++] = node.left;
                }
                if (node.right != null) {
                    queue[r++] = node.right;
                }
            }
            if (isReverse) {
                Collections.reverse(list);
            }
            isReverse = !isReverse;
        }
        return ans;
    }
}
